/*
 * @lc app=leetcode.cn id=1 lang=cpp
 *
 * [1] 两数之和
 *
 * https://leetcode-cn.com/problems/two-sum/description/
 *
 * algorithms
 * Easy (44.96%)
 * Total Accepted:    265.1K
 * Total Submissions: 589.6K
 * Testcase Example:  '[2,7,11,15]\n9'
 *
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * 
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 * 
 * 示例:
 * 
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * 
 * 
 */
#include <vector>
#include <map>
#include <stdio.h>
#include <iostream>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 暴力求解，两次遍历
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {

            for(int j = i + 1; j < nums.size(); j++) {

                if( target - nums[i] == nums[j]) {

                    result.push_back(i);
                    result.push_back(j);
                }
            }
        }

        return result; 
    }

    vector<int> twoSum_map(vector<int>& nums, int target) {
        //使用hash求和，两遍hash表
        // 通过构建hash表用来减少遍历，将O（n）变为O（1）
        map<int, int> hashNums;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {

            /*
            int key = target - nums[i];
            int value = i;
            */
            hashNums.insert(std::pair<int, int>(nums[i], i));
        }

        for(int i = 0; i < nums.size(); i++) {

            int key = target - nums[i];
            if(hashNums.find(key) != hashNums.end() && i != hashNums[key]) {

                result.push_back(i);
                result.push_back(hashNums[key]);
            }
        }
        return result;
    }

    vector<int> twoSum_map_once(vector<int>& nums, int target) {
        //一遍hash表
        map<int, int> hashNum;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            
            int key = nums[i];
            int value = target - nums[i];
            if(hashNum.find(value) == hashNum.end()) {

                hashNum.insert(std::pair<int, int>(nums[i], i));
            }
            else {

                result.push_back(i);
                result.push_back(hashNum[value]);
            }
        }
        return result;
    }
};

int main(int args, char* agrv[]) {
    Solution sol;
    vector<int> nums = {2, 7, 11, 15};
    
    vector<int> result = sol.twoSum(nums, 9);
    if (!result.empty())
        std::cout<< result[0] << " " << result[1] <<std::endl;
    
    result = sol.twoSum_map(nums, 17);
    if (!result.empty())
        std::cout<< result[0] << " " << result[1] <<std::endl;

    result = sol.twoSum_map_once(nums, 9);
    if(!result.empty()) {
        std::cout<< result[0] << " " << result[1] << std::endl;
    }

    getchar();
    return 0;
}

